using System;
using MineFlagger;
using System.Diagnostics;
using System.Text;
using System.Collections;
using System.Drawing;
using System.Threading;

namespace MineFlagger {

	
	
	public class MinesweeperAI {
		GameBoard gameBoard;
		Cell[,] field;
		private Random rnd;

		AIConfig aiConfig;

		IViewer viewer;

        public Boolean abort;
		
		public MinesweeperAI(GameBoard gameBoard, IViewer viewer, AIConfig aiConfig, Random rnd) {
			
			this.rnd = rnd;

			this.gameBoard = gameBoard;
			this.field = gameBoard.Field;
			this.viewer = viewer;

			this.aiConfig = aiConfig;
		}	



		// Kickoff function for using that AI to play the board
		public bool PlayBoard() {
            abort = false;

			ArrayList unresolved = new ArrayList(field.Length);
			foreach (Cell cell in field) {
				unresolved.Add(cell);
			}

            while (unresolved.Count > 0 && !abort)
            {
                if (gameBoard.GameEnded)
                {
                    Debug.Assert(gameBoard.PlayState == PlayState.Won);
                    return gameBoard.PlayState == PlayState.Won;
                }

				//if (aiConfig.ShowSteps) unresolved.Sort();  // Prevents obvious machine looking predictibility 
				unresolved.Sort();

				Cell cellToRemove = null;
			
				// Go through each cell and flag and uncover based on 1 cell anaylsis
				for (int i = 0; i < unresolved.Count; i++) {
					Cell cell = (Cell)unresolved[i];

					if (cell.CellState == CellState.Uncovered) {
						if (cell.NeighboringMines > 0) {

							int neigborsHidden = gameBoard.GetNeighboringHiddenCount(cell); //Key
						
							if (neigborsHidden > 0) {
								int neighboringFlags = gameBoard.GetNeighboringFlagCount(cell); //Key

								if (cell.NeighboringMines - neighboringFlags == neigborsHidden) {
									// Flag all hidden neighbors
									ArrayList neighboringCells = gameBoard.GetNeighbors(cell);
									foreach (Cell nCell in neighboringCells) {
										if (nCell.CellState == CellState.Hidden) {

                                            // Flag Cell (we are sure its a mine)
                                            gameBoard.SetCellState(nCell, CellState.Flagged);

											if (aiConfig.ShowSteps) {
												viewer.InvalidateDirtyCells();
												Thread.Sleep(aiConfig.StepDelay);
											}
										}
									}

									cellToRemove = cell;
									break;

								} else if (cell.NeighboringMines == neighboringFlags) {
									// Show all hidden neighbors
                                    Debug.Assert(!gameBoard.GameEnded);
									bool test = gameBoard.BlockUncover(cell); //////////////////////////////////////////////////////////////////////////
									if (!test) {
										System.Windows.Forms.MessageBox.Show("The AI hit a mine when it was sure it wouldn't!!!");
										throw new Exception();
									}
									cellToRemove = cell;
									if (aiConfig.ShowSteps) {
										viewer.InvalidateDirtyCells();
										Thread.Sleep(aiConfig.StepDelay);
									}
									break;
								}
							
							} else { // Cell has no hidden nieghbros, hence all nieghbors must be mines
								// and hence, the cell must be fufilled 
								cellToRemove = cell;
								break;
							}
						
						} else { // Cell has no neighboring mines
							cellToRemove = cell;
							break;
						}
					
					} else if (cell.CellState == CellState.Flagged) {
						cellToRemove = cell;
						break;
					}
				}

				if (cellToRemove != null) {
					unresolved.Remove(cellToRemove);

                }
                else
                {

                    bool result = false;

                    // Safe Cell AI
                    if (aiConfig.SafeCellAIConfig != null)
                    {
                        //form.StatForm.StartTime();
                        result = SafeCellAI(unresolved, aiConfig.SafeCellAIConfig);
                        //form.StatForm.StopTime("AB3(new)", result);
                    }
                    if (result)
                    {
                        //form.StatForm.lbAB2_Partial.Text = ((int)(int.Parse(form.StatForm.lbAB2_Partial.Text) + 1)).ToString();				
                        continue;
                    }


                    // Flag Path AI
                    if (aiConfig.FlagPathAIConfig != null)
                    {
                        //form.StatForm.StartTime();
                        result = FlagPathAI(unresolved, aiConfig.FlagPathAIConfig);
                        //form.StatForm.StopTime("FillBase2", result);
                    }
                    if (result)
                    {
                        //System.Windows.Forms.MessageBox.Show("FillBase AI Got one");
                        continue;
                    }




                    int minesLeft = gameBoard.MinesRemaining;

                    if (minesLeft == 1)
                    {
                        if (OneMineEndGameAI(unresolved))
                        {
                            //System.Windows.Forms.MessageBox.Show("OneMineEndGmaeAI");
                            //form.StatForm.lbOneMineEndGame.Text = ((int)(int.Parse(form.StatForm.lbOneMineEndGame.Text) + 1)).ToString();
                            continue;
                        }

                    }
                    else if (minesLeft == 0 && unresolved.Count > 0)
                    {
                        //System.Windows.Forms.MessageBox.Show("AllMinesFlagged, cells still hidden");
                        foreach (Cell hiddenCell in unresolved)
                        {
                            if (hiddenCell.CellState == CellState.Hidden)
                            {
                                bool testResult = gameBoard.Uncover(hiddenCell);
                                Debug.Assert(testResult);
                            }
                        }
                        continue;
                    }

                    { // test case: minesLeft == covered cells
                        if (minesLeft == unresolved.Count)
                        {
                            foreach (Cell hiddenCell in unresolved)
                            {
                                // Flag Cell (we are sure its a mine)
                                gameBoard.SetCellState(hiddenCell, CellState.Flagged);
                            }
                        }
                    }


                    if (!aiConfig.UseProbabilityAI)
                    {
                        // Thread.Sleep(100);

                        abort = true;
                        return true;
                    }

                    ArrayList lostProbCells = getLowestProbCells(unresolved);

                    if (lostProbCells.Count > 0)
                    {

                        // Select randomly from the list of cells with the lowest probability of being a mine
                        int i = rnd.Next(0, lostProbCells.Count);
                        Cell rndCell = (Cell)lostProbCells[i];

                        if (!gameBoard.Uncover(rndCell))
                        {
                            Console.WriteLine("Rnd selection hit a mine.  Game over");
                            if (aiConfig.ShowSteps)
                            {
                                viewer.InvalidateDirtyCells();
                                Thread.Sleep(aiConfig.StepDelay);
                            }
                            return false;
                        }

                        // TODO: Check to see if things opend up, if not preform rnd uncover again

                        if (aiConfig.ShowSteps)
                        {
                            viewer.InvalidateDirtyCells();
                            Thread.Sleep(aiConfig.StepDelay);
                        }
                    }
                }
			}

			return true;
		}



		#region AIs


		// If one mine is left, finds and uncovers cells which, if mines, would
		// not fufill all unfufiled and therfor can not be mines.
		public bool OneMineEndGameAI(ArrayList unresolved) {

			if (gameBoard.MinesRemaining != 1) throw new Exception("OneMineEndGameAI only when 1 mines is left.  There is eather more or less then one mine left now.");
			
			ArrayList hCells = GetHiddenCells(unresolved);
			Path path = new Path();
			ArrayList cellsToUncover = new ArrayList();

			foreach (Cell hCell in hCells) {
				path.Add(hCell);
				foreach (Cell unresCell in unresolved) {
					if (unresCell.CellState == CellState.Uncovered &&
						unresCell.NeighboringMines > 0 &&
						unresCell.NeighboringMines != gameBoard.GetNeighboringFlagCount(unresCell, path)) {
						
						cellsToUncover.Add(hCell);
						break;
					}
				}
				path.Clear();
			}

			foreach (Cell cell in cellsToUncover) {
                bool testResult = gameBoard.Uncover(cell);
                Debug.Assert(testResult);
			}			

			return cellsToUncover.Count > 0;
		}

		private ArrayList GetHiddenCells(ArrayList startingList) {
			ArrayList hCells = new ArrayList();
			foreach (Cell cell in startingList) {
				if (cell.CellState == CellState.Hidden) {
					hCells.Add(cell);
				}
			}
			return hCells;
		}

		

		// The Flag Path AI (uses fillBase)
		public bool FlagPathAI(ArrayList unresolved, FlagPathAIConfig fpConfig) {

			bool success = false;

			foreach (Cell cell in unresolved) {

                if (abort) return false;

				if (cell.CellState == CellState.Uncovered &&
					cell.NeighboringMines > 0 &&
					cell.NeighboringMines > gameBoard.GetNeighboringFlagCount(cell)) {
					
					BaseCell bCell = fillBase(new BaseCell(cell), new Path(), fpConfig.FillBaseConfig, fpConfig.FillBaseConfig.Depth);
                    if (bCell == null)
                    {
                        Debug.Assert(abort);
                        return false;
                    }

					if (bCell.Paths.Count == 1) {
						foreach (Cell fCell in (Path)bCell.Paths[0]) {

                            // Flag Cell (we are sure its a mine)
                            gameBoard.SetCellState(fCell, CellState.Flagged);
						
                        }
						// form.StatForm.lbFillBase2.Text = ((int)(int.Parse(form.StatForm.lbFillBase2.Text) + 1)).ToString();
						return success = true;
					
					} else if (bCell.Paths.Count > 1) {
						
						// There are more then one path, but if the same cell exsists in all paths, it must be a mine!

						if (fpConfig.UseSameFlagInAllPaths && ((Path)bCell.Paths[0]).Count > 1) {

							// Find longest path - they all fufill the seme cell so 
							// any path will do (they are all the same size)
							Path lPath = (Path)bCell.Paths[0];

							// For each cell in lPath, check if it exsist in every otehr path
							ArrayList cellsInAllPaths = new ArrayList();

							foreach (Cell cell2 in lPath) {
								bool inAll = true;

								foreach (Path path in bCell.Paths) {
                                    if (abort) return false;

									if (!path.Contains(cell2)) {
										inAll = false;
										break;
									}
								}

								if (inAll) {
									cellsInAllPaths.Add(cell2);
								}
							}

							if (cellsInAllPaths.Count > 0) {
								foreach (Cell cell3 in cellsInAllPaths) {
									
                                    // Flag Cell (we are sure its a mine)
                                    gameBoard.SetCellState(cell3, CellState.Flagged);

									cell3.Marked = true;
								}
								//System.Windows.Forms.MessageBox.Show("This is it");
								if (!success) {
									//form.StatForm.laFBE_allPathsSameFlag.Text = ((int)(int.Parse(form.StatForm.laFBE_allPathsSameFlag.Text) + 1)).ToString();
									return success = true;
								}
							}
						}

						// Make this an option (After 5000 games it wasnt sucsessfull even once)
						// (that is with the AB AI enabled)
						if (fpConfig.UseCellNotInAnyPaths) {

							// Test: see if hidden one or more of the hidden nieghbors is not
							// contained in any of the paths.  If so, it can be uncoverd safely.
						
							// Make list of hidden nighbors
							ArrayList hiddenNCells = gameBoard.GetHiddenNeighbors(bCell.cell);

							if (hiddenNCells.Count > 0) {

								// Iterate thorugh paths removeing each cell from hidden NCells
								bool breakMe = false;
								foreach (Path path20 in bCell.Paths) {
									foreach (Cell fCell20 in path20) {
                                        if (abort) return false;

										hiddenNCells.Remove(fCell20);
										if (hiddenNCells.Count == 0) {
                                            breakMe = true;
											break;
										}
									}
									if (breakMe) break;
								}

								// If any left, uncover
								if (!breakMe && hiddenNCells.Count > 0) {
									foreach (Cell cell20 in hiddenNCells) {
                                        bool testResult = gameBoard.Uncover(cell20);
                                        Debug.Assert(testResult);
									}
									if (!success) {
										//form.StatForm.laFBE_allPathsNoCell.Text = ((int)(int.Parse(form.StatForm.laFBE_allPathsNoCell.Text) + 1)).ToString();
										return success = true;
									}
								}

							}
						}
					
					}
				
				}
			}

			return success;
		}

		
		// Recursive method for the FlagPath AI (also uses the recursive resultingConfounds method)
		private BaseCell fillBase(BaseCell bCell, Path startPath, FillBaseConfig fbConfig, int levels) {

            if (abort) return null;

			// Get all valid paths (and hook up)
			bCell.Paths = EliminateErroneous(GetFlagCombinations(bCell.cell, startPath));

			// Base case conditions [terminations]
			
			if (levels <= 0 ||
				bCell.Paths.Count == 0 ||
				(fbConfig.MaxPaths != -1 && bCell.Paths.Count > fbConfig.MaxPaths)) {

				return bCell;
			}

			// For eliminating deadends
			ArrayList pathsToEliminate = new ArrayList();
 
			// Foreach cell in each path, get unfufiled niegbors and
			// use them as base cells (if they suport valid paths)
			foreach (Path path in bCell.Paths) {
				bool validPath = false;

				// Construct a list of unfufiled cells
				NDArrayList ufnCells = new NDArrayList();
				foreach (FlaggedCell fCell in path) {
					// Chekc to see if we have already determend this fCell (unique to this path) to be fufilled 
					if (!fCell.AllNeighborsFulfilled) {
						ArrayList nCells = GetUnfulfilledNeighboringCellFCellPairs(fCell, path);
						if (nCells.Count != 0) {
							ufnCells.AddRange(nCells);
						} else {
							fCell.AllNeighborsFulfilled = true;
						}
					}
				}

				// Another base case.  Dependent on the limit of new base cells that will be explored recursivly.
				if (fbConfig.MaxNewBaseCells != -1 &&
					ufnCells.Count > fbConfig.MaxNewBaseCells) {
				
					return bCell;
				}

				// All FlaagedCell's neighboring cells are fufiled, check for resulting confounds
				if (ufnCells.Count == 0) {
					if (fbConfig.UseResultingConfounds) {
						validPath = !resultingConfounds(path, 0, fbConfig.ResultingConfoundsConfig);
					} else {
						validPath = true;
					}

				} else {
					foreach (CellFCellPair cfcPair in ufnCells) {
						
						BaseCell newBCell = fillBase(new BaseCell(cfcPair.Cell), path, fbConfig, levels - 1);
                        if (newBCell == null)
                        {
                            Debug.Assert(abort);
                            return null;
                        }

						if (newBCell.Paths.Count > 0) { // As soon as valid, park path with goodness
							cfcPair.FCell.BaseCells.Add(newBCell);
						} 
						
						if (!validPath && (newBCell.Paths.Count > 0 || newBCell.ValidTermination)) {
							validPath = true;
						}
					}
				}

				if (!validPath) {
					pathsToEliminate.Add(path);
				}

			}

			foreach (Path ePath in pathsToEliminate) {
				bCell.Paths.Remove(ePath);
			}

			return bCell;
		}




		// The Safe Cell AI (uses resultingConfounds)
		public bool SafeCellAI(ICollection unresolved, SafeCellAIConfig scConfig) {
			bool success = false;

            
			foreach (Cell cell in field) {
				if (cell.CellState == CellState.Hidden) {
					
					Path path = new Path();
					path.Add(cell);

					if (resultingConfounds(path, 0, scConfig.ResultingConfoundsConfig)) {
						// This cell must not be a mine!
                        Cell c = path[0] as Cell;
						bool testResult = gameBoard.Uncover(gameBoard.Field[c.X, c.Y]);
                        Debug.Assert(testResult);

						success = true;
						break;
					}

				}
			}


			return success;

		}

		
		// Resuctive method for the Safe Cell AI (also used by the fillBase recursive method)
		private bool resultingConfounds(Path path, int callCount, ResultingConfoundsConfig rcConfig) {
			bool result = false;

            if (abort) return false;

			// Keeps track of calls to this method.  It is reset by the client AI for
			// each kickoff of this method.  It hence keeps track of the recurtion depth/breadth
			// and alows for a cut-off base case.
			callCount++;
		
			// List of all the cells that are numberd neighbors of the cells in the path
			NDArrayList numberedNeighbors = new NDArrayList();

			// List of hidden neighbros to the numberedNeighbor cells (not considering path)
			NDArrayList hiddenNeighbors = new NDArrayList();

			// List of unfulfilled neighbors to the hidden neighbors of the numberd neighbors in the path
			NDArrayList cells = new NDArrayList();


			// Go through each flag and get the numberd neighbors
			foreach (FlaggedCell fCell in path) {
				if (!fCell.ConfoundsAnalysisPreformed) {

					numberedNeighbors.AddRange(getUncoveredNumberedNeighbors(fCell));

					// Theoreticly it seems that only fulfilled neighbors could
					// case a confound, but test clearly show this doesnt catch them all.
					// Hence the above, which aparently does.
					//fulfilledCells.AddRange(getFulfilledNeighbors(fCell, path));
					
					fCell.ConfoundsAnalysisPreformed = true;
				}
			}

			if (rcConfig.SearchType == SearchType.Full) {

				// Go through the list of numberd neighbor cells and get thier hidden neighbors (ignoring the path)
				foreach (Cell numberedNeighborCell in numberedNeighbors) {
					hiddenNeighbors.AddRange(gameBoard.GetHiddenNeighbors(numberedNeighborCell));
				}

				// Go through list of numberd neighbor cells, hidden neighbor's and get thier unfufiled nieghbors
				foreach (Cell hNeighbor in hiddenNeighbors) {
					cells.AddRange(GetUnfulfilledNeighbors(hNeighbor, path));
				}

			} else if (rcConfig.SearchType == SearchType.Skimpy) {
				
				// Go through list of numberd neighbor cells and get thier unfufiled nieghbors
				foreach (Cell numberedNeighborCell in numberedNeighbors) {
					cells.AddRange(GetUnfulfilledNeighbors(numberedNeighborCell, path));
				}
			}

			// Analize thoes cells 
			// Full   = [The unfufiled nieghbors, of the hidden nieghbors, of the numbered nieghbors, 
			//           of the flagged cells in the path]
			// Skimpy = [The unfulfiled nieghbors, of the numberd nieghbors, of the flagged cells 
			//           in the path]
			foreach (Cell cell in cells) {

				PathList pList = GetFlagCombinations(cell, path);
				EliminateErroneous(pList);
								
				if (pList.Count == 0) {
					result = true;
					break;
				
				} else if (pList.Count == 1 && rcConfig.RecursiveGoAhead(callCount)) {
				
					if (resultingConfounds((Path)pList[0], callCount, rcConfig)) {
						result = true;
						break;
					}
				}
			}

			return result;
		}


		

		#endregion


		#region Analysis

		public Path SimpleAnalysis() {
			Path path = new Path();
			NDArrayList ndCells = new NDArrayList();
			
			foreach (Cell cell in field) {
				
				if (cell.CellState == CellState.Uncovered &&
					cell.NeighboringMines > 0) {

					int nFlags = gameBoard.GetNeighboringFlagCount(cell);
					if (cell.NeighboringMines > nFlags) {
						
						ArrayList hnCells = gameBoard.GetHiddenNeighbors(cell);

						if (hnCells.Count == cell.NeighboringMines - nFlags) {
							ndCells.AddRange(hnCells);
						
						}
					}
				}

			}

			path.AddRange(ndCells);
			return path;
		}



		// TODO: do something. its very redundent
		public Path SimpleUncover() {
			Path path = new Path();
				
			foreach (Cell cell in field) {
				if (cell.CellState == CellState.Uncovered &&
					cell.NeighboringMines > 0 &&
					cell.NeighboringMines == gameBoard.GetNeighboringFlagCount(cell)) {
					
					// TODO: Shuldent there be a unfufiled list or something (this could
					// be messed up by user unflaging things thoue)
					ArrayList hnCells = gameBoard.GetHiddenNeighbors(cell);
					foreach (Cell hnCell in hnCells) {
						if (!path.Contains(hnCell)) {
							path.Add(hnCell);
						}
					}
				}
			}

			return path;
		}



		public Path AdvancedUncover() {
			Path path = new Path();

			foreach (Cell cell in field) {
				if (cell.CellState == CellState.Hidden) {
					
					Path tempPath = new Path();
					tempPath.Add(cell);

					if (resultingConfounds(tempPath, 0, new ResultingConfoundsConfig())) {
						// This cell must not be a mine!
						path.Add((Cell)tempPath[0]);
					}

				}
			}

			return path;
		}

		
		// TODO: needes updating
		public Path AdvancedAnalysis() {
			Path path = new Path();
			NDArrayList ndCells = new NDArrayList();
			
			foreach (Cell cell in field) {
				if (cell.CellState == CellState.Uncovered &&
					cell.NeighboringMines > 0 &&
					cell.NeighboringMines > gameBoard.GetNeighboringFlagCount(cell)) {
					
					BaseCell bCell = fillBase(new BaseCell(cell), new Path(), new FillBaseConfig(), aiConfig.FlagPathAIConfig.FillBaseConfig.Depth);
                    if (bCell == null)
                    {
                        Debug.Assert(abort);
                        return path;
                    }

					if (bCell.Paths.Count == 1) {
						ndCells.AddRange((ICollection)bCell.Paths[0]);
					}
				}
			}

			path.AddRange(ndCells);
			return path;
		}



		public bool AutoUncover() {
			bool uncover = true;
			
			while (uncover) {
				uncover = false;

				foreach (Cell cell in field) {
					if (cell.CellState == CellState.Uncovered &&
						cell.NeighboringMines > 0 &&
						gameBoard.GetNeighboringHiddenCount(cell) > 0 &&
						cell.NeighboringMines == gameBoard.GetNeighboringFlagCount(cell)) {
					
						bool result = gameBoard.BlockUncover(cell);

						if (!result) return false;

						uncover = true;
					}
				}
			}

			return true;
		}


		#endregion



		

		// Finds the lowest probabilty for a given cell to be a mine
		// Returns an arraylist with all cells on the board with that probabilty
		private ArrayList getLowestProbCells(ArrayList unresolved) {
			float[,] probFiled = new float[gameBoard.Field.GetLength(0), gameBoard.Field.GetLength(1)];
			int[,] probCount = new int[gameBoard.Field.GetLength(0), gameBoard.Field.GetLength(1)];

			int hiddenCellCount = 0;

			foreach (Cell cell in unresolved) {
				
				
				if (cell.CellState == CellState.Uncovered &&
					cell.NeighboringMines != 0 &&
					cell.NeighboringMines > gameBoard.GetNeighboringFlagCount(cell)) {

					ArrayList hnCells = gameBoard.GetHiddenNeighbors(cell);
					int neighboringFlags = gameBoard.GetNeighboringFlagCount(cell);
					
					float newProb = (float)(cell.NeighboringMines - neighboringFlags) / (float)hnCells.Count;

					foreach (Cell hnCell in  hnCells) {
						if (probCount[hnCell.X, hnCell.Y] != 0) {
							float oldWeightedProb = probFiled[hnCell.X, hnCell.Y] * probCount[hnCell.X, hnCell.Y];
							probCount[hnCell.X, hnCell.Y] += 1;
							probFiled[hnCell.X, hnCell.Y] = (oldWeightedProb + newProb) / probCount[cell.X, cell.Y];
						
						} else {
							probFiled[hnCell.X, hnCell.Y] = newProb;
							probCount[hnCell.X, hnCell.Y] += 1;
						}
					}
				} else if (cell.CellState == CellState.Hidden) {
					hiddenCellCount++;
				}
			}

			float seaProb = (float)gameBoard.MinesRemaining / (float)hiddenCellCount;
			int seaCount = 0; // The number of cells that we are seaProb

			// Get lowest probability (of known cells) and set sea probability for all unknown cells
			float lowestProb = 0;
			for (int i = 0; i < probFiled.GetLength(0); i++) {
				for (int j = 0; j < probFiled.GetLength(1); j++) {
					
					// If the Cell is hidden (and only if it is hidden) it is inplay
					if (gameBoard[i, j].CellState == CellState.Hidden) {
						// If the probFiled == 0 for the cell, it must be unknow and shuld be
						// assined seaProb.  Else, the probFiled has already been set and shuld
						// be tested aginst lowest prob and keeped if lowest.
						if (probFiled[i, j] == 0) {
							probFiled[i, j] = seaProb;
							seaCount++;

						} else if (lowestProb == 0 || probFiled[i, j] < lowestProb) {
							lowestProb = probFiled[i, j];
						}
					}
				}
			}

			// If there are seaCells and seaProb is lower then the lowest
			// known cell probability, set lowestProb to seaProb and all the
			// seaCells will be colorected.  If the seaCount is zero, even if
			// the seaProb is less, we dont want to chose it because all hidden cells
			// are of a higher probabilty and no cells will be returned.
			if (seaCount > 0 && (seaProb < lowestProb || lowestProb == 0)) {
				lowestProb = seaProb;
			}

			// Gather all of the lowest probabilities
			ArrayList lowestProbCells = new ArrayList();

			for (int i = 0; i < probFiled.GetLength(0); i++) {
				for (int j = 0; j < probFiled.GetLength(1); j++) {
					if (probFiled[i, j] == lowestProb) {
						lowestProbCells.Add(gameBoard[i, j]);
					}
				}
			}

			return lowestProbCells;
		}
		
		
		


		#region UTIL forAIs #2

		// Returns a ArrayList of CellFCellPairs for niehboring unfufiled cells of fCell
		public ArrayList GetUnfulfilledNeighboringCellFCellPairs(FlaggedCell fCell, Path path) {
			ArrayList nCells = gameBoard.GetNeighbors(fCell);
			ArrayList ufnCells = new NDArrayList(8);

			foreach (Cell nCell in nCells) {
				if (nCell.CellState == CellState.Uncovered &&
					nCell.NeighboringMines > 0 &&
					nCell.NeighboringMines > gameBoard.GetNeighboringFlagCount(nCell, path)) {
					ufnCells.Add(new CellFCellPair(nCell, fCell));
				}
			}

			return ufnCells;
		}

		
		// Returns all unfufilled neighbors
		public ArrayList GetUnfulfilledNeighbors(Cell cell, Path path) {
			ArrayList ufNeighbors = new ArrayList(8);
			
			ArrayList nCells = gameBoard.GetNeighbors(cell);
			foreach (Cell nCell in nCells) {
				if (nCell.CellState == CellState.Uncovered &&
					nCell.NeighboringMines != 0 &&
					nCell.NeighboringMines > gameBoard.GetNeighboringFlagCount(nCell, path)) {
					
					ufNeighbors.Add(nCell);
				}
			}

			return ufNeighbors;
		}

		
		// returns uncoverd cells with >0 neighbhoring mines
		private ArrayList getUncoveredNumberedNeighbors(Cell cell) {
			ArrayList unnCells = new ArrayList(8);
			
			ArrayList nCells = gameBoard.GetNeighbors(cell);
			foreach (Cell nCell in nCells) {
				if (nCell.CellState == CellState.Uncovered &&
					nCell.NeighboringMines != 0) {
					unnCells.Add(nCell);
				}
			}

			return unnCells;
		}


		#endregion
	
		
		#region UTIL for AIs  [Partial Optimization]

		public PathList EliminateErroneous(PathList paths) {
			ArrayList pathsToRemove = new ArrayList();
			
			foreach (Path path in paths) {
				// Set flags
				path.SetCellState(CellState.Flagged, true);
				
				// Test board for mistakes
				if (!TestBoard(path)) {
					pathsToRemove.Add(path);
				}

				// Reset flags
				path.SetCellState(CellState.Hidden, true);
			}

			// Perge erroneous paths
			foreach (Path path in pathsToRemove) {
				paths.Remove(path);
			}

			return paths;		
		}
		

		// Only tests cells neighboring the path passed
		public bool TestBoard(Path path) {
			NDArrayList cells = new NDArrayList();

			foreach (Cell cell in path) {
				cells.AddRange(getUncoveredNumberedNeighbors(cell));
			}

			foreach (Cell cCell in cells) {
				if (cCell.NeighboringMines < gameBoard.GetNeighboringFlagCount(cCell)) {
					return false;
				}
			}

			return true;
		}

		

		// Kickoff to recursive function which gets all posible paths
		// (added on to the path passed) which will fufill the cell passed.
		//  Encoded in intLists and then traslated into PathLists. 
		public PathList GetFlagCombinations(Cell cell, Path path) {
			PathList allPaths = new PathList();

			// Get hidden neigbors (Slots)
			ArrayList hiddenNeighbors = gameBoard.GetHiddenNeighbors(cell, path);
			int slots = hiddenNeighbors.Count;

			// Get flaggs needed (integersNeeded)
			int integersNeeded = cell.NeighboringMines - gameBoard.GetNeighboringFlagCount(cell, path);

			NDArrayList allLists = GetAllIntLists(integersNeeded, slots);

			foreach (NDIntegerList transList in allLists) {
				Path newPath = new Path(path);
				foreach (int i in transList) {
					newPath.Add(hiddenNeighbors[i]);
				}
				allPaths.Add(newPath);
			}

			return allPaths;
		}


		public NDArrayList GetAllIntLists(int integersNeeded, int slots) {
			NDArrayList allLists = new NDArrayList();

			if (integersNeeded == 0) {
				return allLists; // blank list (zero posibilites)

			} else if (integersNeeded == slots) {
				// All slots must be filled, hence only that posibilty exsists
				NDIntegerList transList = new NDIntegerList();
				for (int i = 0; i < slots; i++) {
					transList.Add(i);
				}
				allLists.Add(transList);

			} else if (integersNeeded > slots - integersNeeded) {
				
				NDArrayList inverseList = GetAllIntLists(new NDIntegerList(), slots - integersNeeded, slots);
				
				if (inverseList.Count > 0) {

					foreach (NDIntegerList intList in inverseList) {
						NDIntegerList transList = new NDIntegerList();
						for (int i = 0; i < slots; i++) {
							if (!intList.Contains(i)) {
								transList.Add(i);
							}
						}
						allLists.Add(transList);
					}
				}

			} else {
				allLists = GetAllIntLists(new NDIntegerList(), integersNeeded, slots);
			}

			return allLists;
		}

		public NDArrayList GetAllIntLists(NDIntegerList intList, int integersNeeded, int slots) {
			NDArrayList allLists = new NDArrayList();
	
			if (integersNeeded == 0) return allLists;

			if (integersNeeded > intList.Count) {
				for (int i = 0; i < slots; i++) {
					if (!intList.Contains(i)) { // open slot
						NDIntegerList newList = new NDIntegerList(intList);
						newList.Add(i);
						allLists.AddRange(GetAllIntLists(newList, integersNeeded, slots));
					}
				}

			} else if (integersNeeded == intList.Count) {
				allLists.Add(intList);
			}
			
			return allLists;
		}


		#endregion

    }

    #region AI Config

    public class AIConfig {

		public FlagPathAIConfig FlagPathAIConfig;
		public SafeCellAIConfig SafeCellAIConfig;

		public bool UseOneMineEndOfGameAI;
		public bool UseProbabilityAI;
		
		public bool ShowSteps;
		public int StepDelay = 0;

		public bool ReportData;

		public AIConfig() {
			UseOneMineEndOfGameAI = true;
		}
	}

	public class FlagPathAIConfig {
		public FillBaseConfig FillBaseConfig;

		public bool UseSameFlagInAllPaths;
		public bool UseCellNotInAnyPaths;

		public FlagPathAIConfig() {
			FillBaseConfig = new FillBaseConfig();
			
			UseSameFlagInAllPaths = true;
			UseCellNotInAnyPaths = false;
		}

		public FlagPathAIConfig(FillBaseConfig fbConfig, bool useSameFlagInAllPaths, bool useCellNotInAnyPaths) {
			FillBaseConfig = fbConfig;
		
			UseSameFlagInAllPaths = useSameFlagInAllPaths;
			UseCellNotInAnyPaths = useCellNotInAnyPaths;
		}

	}

	public class SafeCellAIConfig {
		public ResultingConfoundsConfig ResultingConfoundsConfig;
		
		public SafeCellAIConfig() {
			ResultingConfoundsConfig = new ResultingConfoundsConfig();
		}
		public SafeCellAIConfig(ResultingConfoundsConfig rcConfig) {
			ResultingConfoundsConfig = rcConfig;
		}

	}				

	public class FillBaseConfig {
	
		public bool UseResultingConfounds;
		public ResultingConfoundsConfig ResultingConfoundsConfig;

		public int Depth = -1;
		public int MaxPaths = -1;
		public int MaxNewBaseCells = -1;

		#region Constrctros

		public FillBaseConfig() {
			// Set defult
			UseResultingConfounds = true;
			ResultingConfoundsConfig = new ResultingConfoundsConfig();
			
			Depth = 8;
			MaxPaths = 3;
			MaxNewBaseCells = 3;
		}

		public FillBaseConfig(int depth, int maxPaths, int maxNewBaseCells) {
			UseResultingConfounds = false;
			
			Depth = depth;
			MaxPaths = maxPaths;
			MaxNewBaseCells = maxNewBaseCells;
		}

		public FillBaseConfig(int depth, int maxPaths, int maxNewBaseCells, ResultingConfoundsConfig rcConfig) {
			UseResultingConfounds = true;
			ResultingConfoundsConfig = rcConfig;
			
			Depth = depth;
			MaxPaths = maxPaths;
			MaxNewBaseCells = maxNewBaseCells;
		}

		#endregion
	}

	public enum SearchType { Full, Skimpy }
	public class ResultingConfoundsConfig {
		// Call dependent (must be reset for each use)
		
		
		public SearchType SearchType;
		
		public bool UseRecursively;
		public int RecursionLimit;


		#region Constructors

		public ResultingConfoundsConfig() {
			// Set defults
			SearchType = SearchType.Full;
			UseRecursively = true;
			RecursionLimit = 100;
		}

		public ResultingConfoundsConfig(SearchType searchType, bool useRecursively, int recursionLimit) {
			SearchType = searchType;
			UseRecursively = useRecursively;
			RecursionLimit = recursionLimit;
		}

		#endregion

		public bool RecursiveGoAhead(int callCount) {
			if (UseRecursively) {
				if (RecursionLimit == -1 || RecursionLimit > callCount) {
					// no limit OR limit not reached
					return true;
				}
			}
			
			// no rescursive use alowed OR limit was reached
			return false;
		}

    }

    #endregion



    public class NDIntegerList : ArrayList {
		

		public NDIntegerList(ICollection c) : base(c){}
		public NDIntegerList() : base() {}
		public NDIntegerList(int i) : base(i) {}

		override public int Add(object obj) {
			if (obj is int) {
				int newInt = (int)obj;

				for (int i = 0; i < this.Count; i++) {
					if (newInt < (int)this[i]) {
						this.Insert(i, newInt);
						return i;
					
					} else if (newInt == (int)this[i]) {
						return -1;
					}
				}
				
				// Has not reutned, hence just add (to bottom)
				return base.Add(newInt);

			}

			return -1;
		}

		override public void AddRange(ICollection c) {
			foreach (object o in c) {
				this.Add(o);
			}
		}

		override public bool Equals(Object obj) {
			if (obj is NDIntegerList && ((NDIntegerList)obj).Count == this.Count) {
				NDIntegerList ndIntList = (NDIntegerList)obj;
				
				for (int i = 0; i < this.Count; i++) {
					if (!ndIntList[i].Equals(this[i])) {
						return false;
					}
				}
				
				return true;
			}
			return false;
		}
        public override int GetHashCode()
        {
            throw new NotSupportedException();
        }

		override public string ToString() {
			StringBuilder sb = new StringBuilder();

			if (this.Count > 0) {
				for (int i = 0; i < this.Count - 1; i++) {
					sb.Append(this[i].ToString() + ", ");
				}

				sb.Append(this[this.Count - 1].ToString());
			}

			return sb.ToString();
		}
	}

	

	#region FillBase Tree structure classes
	
	public class PathList : ArrayList, IComparable {
		
		override public int Add(object obj) {
			if (obj is Path) {
				if (!this.Contains(obj)) {
					return base.Add(obj);
				}
			}
			return -1;
		}

		override public void AddRange(ICollection c) {
			foreach (object o in c) {
				if (o is Path) {
					this.Add(o);
				}
			}
		}

		public int CompareTo(object obj) {
			if (obj is PathList) {
				if (this.Count == ((PathList)obj).Count) {
					return 0;
				} else if (this.Count < ((PathList)obj).Count) {
					return -1;
				} else { // this.Count > ((PathList)obj).Count
					return 1;
				}
			}
			return 1;
		}

		private int pathCursor = -1;


		// Switches through paths
		public void MarkNextPath() {
			if (this.Count == 0) return;
			
			if (pathCursor != -1) {
				((Path)this[pathCursor]).MarkPath(false);
			}

			if (pathCursor + 1 >= this.Count) {
				pathCursor = -1;
			}

			pathCursor++;

			((Path)this[pathCursor]).MarkPath(true);
		}

		public void MarkPath(int index) {
			// unmark all paths
			foreach (Path path in this) {
				path.MarkPath(false);
			}

			// mark spesific path
			((Path)this[index]).MarkPath(true);
		}
	}

	public class NDArrayList : ArrayList {
		public NDArrayList() : base() {}
		public NDArrayList(int i) : base(i) {}
		public NDArrayList(ICollection c) : base() {
			AddRange(c);
		}

		override public int Add(object obj) {
			if (!this.Contains(obj)) {
				return base.Add(obj);
			}

			return -1;
		}

		override public void AddRange(ICollection c) {
			foreach (object o in c) {
				this.Add(o);
			}
		}
	}

	public class Path : ArrayList {
		
		public Path(ICollection c) : base(c){}
		public Path() : base() {}
		public Path(int i) : base(i) {}

		override public int Add(object obj) {
			if (obj is Cell) {
				
				FlaggedCell newCell;
				if (obj is FlaggedCell) {
					newCell = (FlaggedCell)obj;
				} else {
					newCell = new FlaggedCell((Cell)obj);
				}

				for (int i = 0; i < this.Count; i++) {
					Cell cell = (Cell)this[i];
					if (newCell.X > cell.X) {
						continue;
					} else if (newCell.X == cell.X && newCell.Y > cell.Y) {
						continue;
					} else {
						this.Insert(i, newCell);
						return i;
					}
				}

				return base.Add(newCell);

			} else {
				return -1;
			}
		}

		override public bool Equals(Object obj) {
			if (obj is Path && ((Path)obj).Count == this.Count) {
				Path path = (Path)obj;
				
				for (int i = 0; i < this.Count; i++) {
					if (!path[i].Equals(this[i])) {
						return false;
					}
				}
				
				return true;
			}
			return false;
		}
        public override int GetHashCode()
        {
            throw new NotSupportedException();
        }

		public void MarkPath(bool marked) {
			foreach (Cell cell in this) {
				cell.Marked = marked;
			}
		}

		public void MarkPath(bool marked, Color color) {
			foreach (Cell cell in this) {
				cell.Marked = marked;
				cell.MarkColor = color;
			}
		}

		public void PrintPath() {
			Console.WriteLine("Count = {0}", this.Count.ToString());
			foreach (Cell cell in this) {
				Console.WriteLine("({0}, {1})", cell.X.ToString(), cell.Y.ToString());
			}
		}

		public void SetCellState(CellState cellState) {
			foreach (Cell cell in this) {
				cell.CellState = cellState;
			}
		}

		public void SetCellState(CellState cellState, bool suppressDrawing) {
			foreach (Cell cell in this) {
				bool oState = cell.SuppressDrawing;
				
				cell.SuppressDrawing = suppressDrawing;
				cell.CellState = cellState;
				
				cell.SuppressDrawing = oState;
			}
		}

	
	}


	#endregion
}
